package com.lwt.codetop.dp;

// 72. 编辑距离

/**
 * 思路：dp
 * 状态表示：f[i][j]: a[0~i]变为b[0~j]的最少操作次数
 * 状态转移（分类：插入/删除/替换）：
 *          插入a[i](插入后a == b说明没有插入前a[0~i] == b[0~j-1]了)：f[i][j] = f[i][j - 1] + 1
 *          删除a[i](删除后a == b说明没有删除前a[0~i-1] == b[0~j]了)：f[i][j] = f[i - 1][j] + 1
 *          替换a[i]：
 *                  若果a[i] == b[j]：不用替换 f[i][j] = f[i - 1][j - 1]
 *                  不等：(替换后a == b说明没有替换前a[0~i-1] == b[0~j-1]了)：f[i][j] = f[i - 1][j - 1] + 1
 *                      f[i][j] = f[i - 1][j - 1] + 1
 * 属性：min
 * 初始化：当a为空时，要进行len(b)次插入；
 *       当b为空时，要进行len(a)次删除；
 *
 */
public class EditDistance {
    public static void main(String[] args) {
        // 构建测试用例
        String a = "intention",  b = "execution";
        int res = minDistance(a, b);
        System.out.println(res);
    }

    private static int minDistance(String a, String b) {
        int n = a.length(), m = b.length();
        // 下标从1开始
        a = " " + a;
        b = " " + b;
        int[][] f = new int[n + 10][m + 10];
        // 初始化
        for (int i = 0; i <= n; i++) f[i][0] = i;
        for (int i = 0; i <= m; i++) f[0][i] = i;
        // dp
        for (int i =1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 插入/删除a[i]
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + 1;
                if(a.charAt(i) == b.charAt(j)) f[i][j] = f[i - 1][j - 1];
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return f[n][m];
    }
}
